package day1022;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author 比特就业课
 * @Date 2022-10-20
 */
public class BinaryTree {
    // 定义一个表示节点的类
    private static class TreeNode {
        int value; // 当前节点的值
        TreeNode left;  // 左子树的引用
        TreeNode right; // 右子树的引用
        // 构造方法

        public TreeNode(int value) {
            this.value = value;
        }
    }

    // 根节点的引用
    public TreeNode root;

    /**
     * 为了演示方便通过硬代码的方式创建一个二叉树
     * 后续不会通过这样的方式去创建二叉树
     */
    public void create () {
        // 先所有的节点创建出来
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        // 处理引用关系
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node5.right = node8;
        node3.left = node6;
        node3.right = node7;
        // 指定根节点的引用
        root = node1;
    }

    // 前序遍历

    /**
     * 前序遍历
     * @param root 根——左右
     */
    public void preOrder(TreeNode root) {
        if(root==null){
            return;
        }
//        处理根节点
        System.out.print(root.value+" ");
//        处理左子树
        preOrder(root.left);
//        处理右子树
        preOrder(root.right);
    }

    /**
     *
     * @param root
     * 左-根-右
     */
    public void inOrder(TreeNode root) {
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.value+" ");
        inOrder(root.right);
    }

    /**
     * 后序遍历
     * @param root
     * 左右根
     */
    public void postOrder(TreeNode root) {
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value+" ");
    }

    static  int  count=0;
    // 获取树中节点的个数
    public int size(TreeNode root) {
//        if(root==null){
//            return 0;
//        }
//        return size(root.left)+size(root.right)+1;
        if(root==null){
            return 0;
        }
        size(root.left);
        count++;
        size(root.right);
        return count;
    }

    // 获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null && root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

// 子问题思路-求叶子结点个数

    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k) {
        if(root==null || k<=0){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    // 获取二叉树的高度
// https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/submissions/375238559/
    public int getHeight(TreeNode root) {

        return 0;
    }

    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, int val) {
        if(root==null){
            return null;
        }
        if(root.value==val){
            return root;
        }
        TreeNode leftFind=find(root.left,val);
        TreeNode rightFind=find(root.right,val);
        if(leftFind==null && rightFind==null){
            return null;
        }else {
            if(leftFind!=null){
                return leftFind;
            }
            if(rightFind!=null){
                return rightFind;
            }
        }
        return null;
    }

    //层序遍历
    public void levelOrder(TreeNode root) {
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node=queue.poll();
            System.out.print(node.value+" ");
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {

        return false;
    }
}
